/**
 * 563. 背包问题 V
 * 给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
 * 每一个物品只能使用一次
 * *https://www.lintcode.com/problem/backpack-v/description
 *
 * 样例
 * 给出候选物品集合 [1,2,3,3,7] 以及 target 7
 *
 * 结果的集合为:
 * [7]
 * [1,3,3]
 * 返回 2
 *
 * @author jeymingwu
 * @date 2019/9/30 10:54
 */
public class L0563_Backpack_V {

    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int target) {
        int[][] dp = new int[nums.length + 1][target + 1];

        for (int i = 0; i <= nums.length; ++i) {
            for (int j = 0; j <= target; ++j) {
                dp[i][j] = 0;
                if (j == 0) {
                    dp[i][j] = 1;
                }
                if (i - 1 >= 0) {
                    if (j - nums[i - 1] >= 0) {
                        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }

        for (int i = 0; i <= nums.length; ++i) {
            for (int j = 0; j <= target; ++j) {
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }

        return dp[nums.length][target];
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1};
        int[] nums2 = {1, 2, 3, 3, 7};
        L0563_Backpack_V backpackV0563 = new L0563_Backpack_V();
        System.out.println(backpackV0563.backPackV(nums, 3));
        System.out.println(backpackV0563.backPackV(nums2, 7));
    }
}
